package 剑指offer.树;

import java.util.ArrayList;
import java.util.Stack;

/*
请实现一个函数按照之字形打印二叉树，
即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，
第三行按照从左到右的顺序打印，其他行以此类推。
 */
public class 第32题第3小题之字形打印二叉树 {

    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /*
        解法：
        其实就是按照 Z 字形打印
        第一行向右打印
        第二行向左打印

        也就是奇数行从做到右打印
        偶数行从右到左打印

        使用两个栈，一个用来保存执行奇数行的时候下一行的数据
        另一个用来保存执行偶数行的时候，保存下一个行的数据

        当前如果在第一行，第一行只有一个元素，可以事先直接添加到stack1，然后输出第一行之后把第一行下面的元素按照从右到左，也就是压入子节点的【左】【右】子树
        如果在第二行，应该从右往左输出，输出一个元素应该保存接下来一行要输出的数据，也就是保存节点的【右】【左】节点
     */
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (pRoot == null) {
            return ans;
        }
        Stack<TreeNode> stack1 = new Stack<>(); // 保存奇数行的节点
        Stack<TreeNode> stack2 = new Stack<>(); // 保存偶数行的节点
        int level = 0; // 记录行数
        stack1.push(pRoot);
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            level++;
            ArrayList<Integer> tmp = new ArrayList<>();
            // 当前处于奇数层
            while ((level & 1) != 0 && !stack1.isEmpty()) {
                TreeNode node = stack1.pop();
                tmp.add(node.val);
                // 下面的偶数行从右开始输出的话，应该先压左节点，再压右节点
                if (node.left != null) {
                    stack2.push(node.left);
                }
                if (node.right != null) {
                    stack2.push(node.right);
                }
            }
            // 当前处于偶数层
            while ((level & 1) == 0 && !stack2.isEmpty()) {
                TreeNode node = stack2.pop();
                tmp.add(node.val);
                if (node.right != null) {
                    stack1.push(node.right);
                }
                if (node.left != null) {
                    stack1.push(node.left);
                }
            }
            ans.add(new ArrayList<>(tmp));
        }
        return ans;
    }
}
